package com.mccken.practice.top100.Top_30$.Top_32;

import java.util.PriorityQueue;

import com.mccken.practice.top100.ListNode;

/**
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2024-02-28 22:03
 **/
public class MergeKLists {
	
	PriorityQueue<ListNode> pq = new PriorityQueue<>((o1,o2)-> o1.val - o2.val);
	
	public ListNode mergeKLists(ListNode[] lists) {
		// 只需要把每个链表的头结点放到堆中就可以了，由堆来比较大小，随后取出一个再offer进一个
		for (ListNode node : lists) {
			if (node != null){
				pq.offer(node);
			}
		}
		
		ListNode dummy = new ListNode(0);
		ListNode cur = dummy;
		
		while (!pq.isEmpty()) {
			ListNode s = pq.poll();
			cur.next = s;
			cur = cur.next;
			s = s.next;
			if (s!=null) {
				pq.offer(s);
			}
		}
		
		return dummy.next;
	}
	
}
